package summary;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/29 23:44
 * https://leetcode-cn.com/problems/path-sum-iii/
 */
public class Title437 {

    static class TreeNode {
        int val;

        TreeNode left;

        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        //从当前节点出发
        int result = dfs(root, targetSum);
        result += pathSum(root.left, targetSum);
        result += pathSum(root.right, targetSum);
        return result;
    }

    private int dfs(TreeNode root, int targetSum) {
        int count = 0;
        targetSum -= root.val;
        if (targetSum == 0) {
            count++;
        }
        if (root.left != null) {
            count += dfs(root.left, targetSum);
        }
        if (root.right != null) {
            count += dfs(root.right, targetSum);
        }
        return count;
    }

    public static int pathSum1(TreeNode root, int targetSum) {
        //存放(前缀和, 出现的次数)
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs1(root, prefix, 0, targetSum);
    }

    public static int dfs1(TreeNode root, Map<Long, Integer> prefix, long cur, int targetSum) {
        if (root == null) {
            return 0;
        }
        //计算前缀和
        cur += root.val;
        int count = prefix.getOrDefault(cur - targetSum, 0);
        //将当前节点的前缀和放入map集合中
        prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
        count += dfs1(root.left, prefix, cur, targetSum);
        count += dfs1(root.right, prefix, cur, targetSum);
        prefix.put(cur, prefix.getOrDefault(cur, 0) - 1);
        return count;
    }





    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode root1 = new TreeNode(4);
        TreeNode root2 = new TreeNode(8);
        TreeNode root3 = new TreeNode(11);
        TreeNode root4 = new TreeNode(13);
        TreeNode root5 = new TreeNode(4);
        TreeNode root6 = new TreeNode(7);
        TreeNode root7 = new TreeNode(2);
        TreeNode root9 = new TreeNode(5);
        TreeNode root10 = new TreeNode(1);
        root.left = root1;
        root.right = root2;
        root1.left = root3;
        root2.left = root4;
        root2.right = root5;
        root3.left = root6;
        root3.right = root7;
        root5.left = root9;
        root5.right = root10;
        pathSum1(root, 22);
    }
}
